package at.fhooe.mc.task01;

public class BinarySearchTree {

	/** Inner class for the binary tree node. **/
	protected class BinaryTreeNode {
		public BinaryTreeNode left;
		public BinaryTreeNode right;
		public int data;

		public BinaryTreeNode(int elem) {
			data = elem;
			left = null;
			right = null;
		}
	}

	/** Root node of the tree. **/
	protected BinaryTreeNode root;

	/** Number of elements stored in the tree. */
	protected int size;

	BinarySearchTree(BinaryTreeNode root) {

		this.root = root;

	}

	BinarySearchTree() {
		this.root = null;
	}

	private boolean insertSubTree(BinaryTreeNode prev, BinaryTreeNode actual,
			int elem) {

		if (elem < actual.data) {
			actual = actual.left;
			if (actual == null) {
				BinaryTreeNode newNode = new BinaryTreeNode(elem);
				prev.left = newNode;
				return true;
			} else {
				prev = prev.left;
				return insertSubTree(prev, actual, elem);

			}

		} else if (elem > actual.data) {

			actual = actual.right;
			if (actual == null) {
				BinaryTreeNode newNode = new BinaryTreeNode(elem);
				prev.right = newNode;
				return true;
			} else {
				prev = prev.right;
				return insertSubTree(prev, actual, elem);

			}
		} else {
			return false;

		}
	}

	/**
	 * Inserts the given element. Duplicate elements are not allowed. Returns
	 * true if insertion was successful, false otherwise.
	 */
	public boolean insert(int elem) {
		size++;
		BinaryTreeNode prev;
		BinaryTreeNode actual;
		actual = root;
		prev = root;

		if (root == null) {
			root = new BinaryTreeNode(elem);
			return true;
		}

		return insertSubTree(prev, actual, elem);

	}

	private boolean findSubTree(BinaryTreeNode actual, int key) {

		if (actual == null) {
			return false;
		}

		if (key < actual.data) {

			if (actual.left == null) {
				return false;
			}
			actual = actual.left;
			if (key == actual.data) {

				return true;
			} else {

				return findSubTree(actual, key);

			}

		} else if (key > actual.data) {

			if (actual.right == null) {
				return false;
			}

			actual = actual.right;
			if (key == actual.data) {

				return true;

			} else {

				return findSubTree(actual, key);

			}

		} else {
			return false;
		}

	}

	/**
	 * Searches for the (first) element with the given key. Returns true if it
	 * could be found, false otherwise.
	 */
	public boolean find(int key) {

		BinaryTreeNode actual;
		actual = root;

		if (root == null) {
			return false;
		}

		return findSubTree(actual, key);

	}

	public int elements(BinaryTreeNode actual, int counter) {

		if (actual.left == null && actual.right == null) {
			counter++;
			return counter;
		}

		if (actual.left != null) {
			counter = elements(actual.left, counter);
		}

		counter++;

		if (actual.right != null) {

			counter = elements(actual.right, counter);
		}

		return counter;

	}

	/**
	 * * Removes the element with the given key. Returns true if the key could
	 * be * found (and removed), false otherwise.
	 */
	public boolean remove(int key) {
		boolean isTrue=false;
		isTrue = remove(root, key);
		this.size=this.elements(root, 0);
		return isTrue;
	}

	private boolean remove(BinaryTreeNode actual, int key) {
		BinaryTreeNode n, p, parent, succ;
		parent = null;
		p = actual;
		while (p != null && p.data != key) {
			parent = p;
			if (key < p.data) {
				p = p.left;
			} else {
				p = p.right;
			}
		}
		n = p;
		if (n == null) {
			return false;
		}
		if (n.right == null) {
			
			p = n.left;
		} else if (n.right.left == null) {
			
			p = n.right;
			p.left = n.left;
		} else {
			
			succ = n.right;
			while (succ.left.left != null)
				succ = succ.left;
			p = succ.left;
			succ.left = p.right;
			p.left = n.left;
			p.right = n.right;
		}
		if (parent == null) {
			root = p;
		} else if (key < parent.data) {
			parent.left = p;
		} else {
			parent.right = p;
		}
		return true;
	}

	/** Returns the number of elements stored in the tree. */
	public int size() {

		return size;
	}

	private int getSubParent(BinaryTreeNode actual, BinaryTreeNode prev, int key) {

		if (key < actual.data) {
			prev = actual;
			actual = actual.left;
			if (key == actual.data) {

				return prev.data;
			} else {

				return getSubParent(actual, prev, key);

			}

		} else if (key > actual.data) {
			prev = actual;
			actual = actual.right;
			if (key == actual.data) {
				return prev.data;
			} else {

				return getSubParent(actual, prev, key);

			}

		} else {
			return prev.data;
		}

	}

	/**
	 * Returns the parent element of the given key. Integer.MIN_VALUE if no
	 * parent can be found.
	 */
	public int getParent(int key) {

		BinaryTreeNode actual, prev;
		actual = root;
		prev = root;

		if (size() < 2 || find(key) == false) {
			return Integer.MIN_VALUE;
		} else {

			return getSubParent(actual, prev, key);

		}

	}

	private int toArray(int[] arr, BinaryTreeNode actual, int pointer) {

		if (actual.left == null && actual.right == null) {

			arr[pointer++] = actual.data;
			return pointer;
		}

		if (actual.left != null) {

			pointer = toArray(arr, actual.left, pointer);
		}

		arr[pointer++] = actual.data;

		if (actual.right != null) {

			pointer = toArray(arr, actual.right, pointer);
		}

		return pointer;

	}

	/**
	 * Returns the elements of the tree in ascending (inorder traversal) or
	 * descending (reverse inorder traversal) order.
	 */
	public int[] toArray(boolean ascending) {

		int[] inOrder = new int[size];
		int pointer = 0;

		if (size == 0) {
			return inOrder;
		}

		toArray(inOrder, root, pointer);

		if (ascending == true) {
			return inOrder;
		} else {
			int[] inOrderDescending = new int[inOrder.length];

			for (int k = 0, i = inOrder.length - 1; i >= 0; i--) {
				inOrderDescending[k++] = inOrder[i];
			}

			return inOrderDescending;

		}
	}

	private int toArrayPostOrder(int[] arr, BinaryTreeNode actual,
			BinaryTreeNode prev, int pointer) {

		if (actual.left == null && actual.right == null) {

			return pointer;
		}

		if (actual.left != null) {

			prev = actual;
			actual = actual.left;
			pointer = toArrayPostOrder(arr, actual, prev, pointer);
			arr[pointer++] = actual.data;
		}

		if (prev == root) {
			actual = prev.right;

			pointer = toArrayPostOrder(arr, actual, prev, pointer);
		}

		if (prev.right != null) {
			arr[pointer++] = prev.right.data;
		}

		if (prev == root) {
			arr[pointer++] = prev.data;
		}

		return pointer;

	}

	/** Returns the elements of the tree (postorder traversal). */
	public int[] toArrayPostOrder() {

		int[] postOrder = new int[size];
		int pointer = 0;

		if (size == 0) {
			return postOrder;
		}

		toArrayPostOrder(postOrder, root, root, pointer);

		return postOrder;

	}

	private int toArrayPreOrder(int[] arr, BinaryTreeNode actual, int pointer) {

		if (actual == null)
			return pointer;

		arr[pointer++] = actual.data;
		pointer = toArrayPreOrder(arr, actual.left, pointer);
		pointer = toArrayPreOrder(arr, actual.right, pointer);

		return pointer;

	}

	/** Returns the elements of the tree (preorder traversal). */
	public int[] toArrayPreOrder() {

		int[] preOrder = new int[size];
		int pointer = 0;

		if (size == 0) {
			return preOrder;
		}

		toArrayPreOrder(preOrder, root, pointer);

		return preOrder;

	}

	/**
	 * Returns largest number stored in the tree. Integer.MIN_VALUE if no
	 * largest element can be found
	 */
	public int max() {

		BinaryTreeNode prev = root;
		BinaryTreeNode actual = root;

		if (size == 0) {

			return Integer.MIN_VALUE; //.....

		} else {

			actual = actual.right;

			while (actual != null) {

				actual = actual.right;
				prev = prev.right;

			}

			return prev.data;

		}

	}

	/**
	 * Returns smallest number
	 * 
	 * /** Returns smallest number stored in the tree. Integer.MIN_VALUE if no
	 * smallest element can be found
	 */
	public int min() {

		BinaryTreeNode prev = root;
		BinaryTreeNode actual = root;

		if (size == 0) {

			return Integer.MIN_VALUE; //....

		} else {

			actual = actual.left;

			while (actual != null) {

				actual = actual.left;
				prev = prev.left;

			}

			return prev.data;

		}

	}

	/** Represents the tree in a human readable form. */
	public String toString() {
		return toString("", root); // the outprint is turned left
	}

	private static String toString(String output, BinaryTreeNode actual) {
		if (actual == null) {
			return "";
		}
		String string = output + actual.data;
		if (actual.right != null)
			string = toString(" " + output, actual.right) + "\n" + string;
		if (actual.left != null)
			string = string + "\n" + toString(" " + output, actual.left);
		return string;
	}
}
